package 代码随想录.链表.删除链表的倒数第N个节点;

import java.util.List;

/**lc19. 删除链表的倒数第 N 个结点
 * link：https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/
 * @author ChenweiLin
 * @create 2021-12-07 21:30
 */
public class removeNthNodeFromEndOfList {
    public static void main(String[] args) {



    }
    class ListNode {
        int val;
        ListNode next;
        ListNode() {}
        ListNode(int val) { this.val = val; }
        ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    }

    public ListNode removeNthFromEnd(ListNode head, int n) {
        //特殊情况
        if (head.next == null && n == 1){
            return null;
        }
        //伪头节点+固定长度的双指针
        ListNode wei = new ListNode(0,head);
        //第一个指针节点
        ListNode before = wei;
        //思路：删除倒数第n个节点，即删除正数第k-n+1个节点,与第一个节点差距k-n
        //第二个指针节点为第一个指针节点后第n+1个节点，
        ListNode after = before;
        for (int i = 0; i < n+1; i++) {
            after = after.next;
        }

        while (after != null){//直到after == null，此时 before在需要交换的节点的前一个节点上
            before = before.next;
            after = after.next;
        }

        //删除该节点
        before.next = before.next.next;

        return wei.next;

    }
}

